package com.zl.learning.arithmetic.leetcode;

public class TestKMP2 {

    private static int[] getNext(String t) {
        int i = 0, j = -1;
        int[] next = new int[t.length() + 1];
        next[0] = -1;
        while (i < t.length()) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    private static int kmp(String s, String t) {
        int i = 0;
        int j = 0;
        int[] next = getNext(t);
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= t.length()) {
            return i - t.length();
        }
        return -1;
    }

    public static void main(String[] args) {
        String s = "abcabcdf";
        String t = "abcd";
        int index = kmp(s,t);
        System.out.println(index);
    }
}
